package com.asa.suanfa;

import java.util.Arrays;

import com.asa.suanfa.bean.ElemType;

/**
 * 基础算法方法类
 */
public class SUtils {

	/*****************八大排序算法。。。都是内部排序**********************/
	
	/**
	 * 1，直接插入排序（ Straight Insertion Sort）
	 * 
	 * @param a 数组
	 * @return	
	 */
	public static double[] insertSort(double a[]){
		for(int i= 1; i<a.length; i++){  
	        if(a[i] < a[i-1]){               //若第i个元素大于i-1元素，直接插入。小于的话，移动有序表后插入  
	            int j= i-1;   
	            double x = a[i];        //复制为哨兵，即存储待排序元素  
	            a[i] = a[i-1];           //先后移一个元素  
	            while(x < a[j]){  //查找在有序表的插入位置  
	                a[j+1] = a[j];  
	                j--;         //元素后移  
	            }  
	            a[j+1] = x;      //插入到正确位置  
	        }  
	        //System.out.println(a+"        "+a.length+"         "+i);           //打印每趟排序的结果  
	    }
		return a;
	}
	
	/**
	 *  2,插入排序—希尔排序（Shell`s Sort）
	 * 	这个不稳定，还很麻烦就不写了
	 */
	
	
	/**
	 * 3. 选择排序—简单选择排序（Simple Selection Sort）
	 *
	 */
	static void selectSort(int a[]){  
	    int key, tmp;  
	    for(int i = 0; i< a.length; ++i) {  
	        key = selectMinKey(a,i);           //选择最小的元素  
	        if(key != i){  
	            tmp = a[i];  a[i] = a[key]; a[key] = tmp; //最小元素与第i位置元素互换  
	        }  
	         
	    }  
	}  
	static int selectMinKey(int a[], int i)  
	{  
	    int k = i;  
	    for(int j=i+1 ;j< a.length; ++j) {  
	        if(a[k] > a[j]) k = j;  
	    }  
	    return k;  
	}  

	/**
	 * 4. 选择排序—堆排序（Heap Sort）
	 * 
	 */
	public static void heapSort(int H[],int length)  
	{  
	    //初始堆  
	    BuildingHeap(H, length);  
	    //从最后一个元素开始对序列进行调整  
	    for (int i = length - 1; i > 0; --i)  
	    {  
	        //交换堆顶元素H[0]和堆中最后一个元素  
	        int temp = H[i]; H[i] = H[0]; H[0] = temp;  
	        //每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整  
	        HeapAdjust(H,0,i);  
	  }  
	}  
	/** 
	 * 初始堆进行调整 
	 * 将H[0..length-1]建成堆 
	 * 调整完之后第一个元素是序列的最小的元素 
	 */  
	public static void BuildingHeap(int H[], int length)  
	{   
	    //最后一个有孩子的节点的位置 i=  (length -1) / 2  
	    for (int i = (length -1) / 2 ; i >= 0; --i)  
	        HeapAdjust(H,i,length);  
	} 
	
	/** 
	 * 已知H[s…m]除了H[s] 外均满足堆的定义 
	 * 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,  
	 * 
	 * @param H是待调整的堆数组 
	 * @param s是待调整的数组元素的位置 
	 * @param length是数组的长度 
	 * 
	 */  
	public static void HeapAdjust(int H[],int s, int length)  
	{  
	    int tmp  = H[s];  
	    int child = 2*s+1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
	    while (child < length) {  
	        if(child+1 <length && H[child]<H[child+1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
	            ++child ;  
	        }  
	        if(H[s]<H[child]) {  // 如果较大的子结点大于父结点  
	            H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点  
	            s = child;       // 重新设置s ,即待调整的下一个结点的位置  
	            child = 2*s+1;  
	        }  else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出  
	             break;  
	        }  
	        H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
	    }  
//	    print(H,length);  
	}  
	  
	/**
	 * 5. 交换排序—冒泡排序（Bubble Sort）
	 * 
	 */
	public static void bubbleSort(int a[], int n){  
	    for(int i =0 ; i< n-1; ++i) {  
	        for(int j = 0; j < n-i-1; ++j) {  
	            if(a[j] > a[j+1])  
	            {  
	                int tmp = a[j] ; a[j] = a[j+1] ;  a[j+1] = tmp;  
	            }  
	        }  
	    }  
	}  
	/**
	 * 对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：
	 * ①设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。
	 * @param r
	 * @param n
	 */
	public static void bubble_1 ( int r[], int n) {  
	    int i= n -1;  //初始时,最后位置保持不变  
	    while ( i> 0) {   
	        int pos= 0; //每趟开始时,无记录交换  
	        for (int j= 0; j< i; j++)  
	            if (r[j]> r[j+1]) {  
	                pos= j; //记录交换的位置   
	                int tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
	            }   
	        i= pos; //为下一趟排序作准备  
	     }   
	}    
	
	/**
	 * ②传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。
	 * @param r
	 * @param n
	 */
	public static void bubble_2 ( double r[], int n){  
	    int low = 0;   
	    int high= n -1; //设置变量的初始值  
	    double tmp;
	    int j;  
	    while (low < high) {  
	        for (j= low; j< high; ++j) //正向冒泡,找到最大者  
	            if (r[j]> r[j+1]) {  
	                tmp = r[j]; r[j]=r[j+1];r[j+1]=tmp;  
	            }   
	        --high;                 //修改high值, 前移一位  
	        for ( j=high; j>low; --j) //反向冒泡,找到最小者  
	            if (r[j]<r[j-1]) {  
	                tmp = r[j]; r[j]=r[j-1];r[j-1]=tmp;  
	            }  
	        ++low;                  //修改low值,后移一位  
	    }   
	}   
	
	
	/**
	 * 6. 交换排序—快速排序（Quick Sort
	 * 
	 */
	public static void quickSort(int a[], int low, int high){  
	    if(low < high){  
	        int privotLoc = partition(a,  low,  high);  //将表一分为二  
	        quickSort(a,  low,  privotLoc -1);          //递归对低子表递归排序  
	        quickSort(a,   privotLoc + 1, high);        //递归对高子表递归排序  
	    }  
	}  
	
	public static int partition(int a[], int low, int high)  
	{  
	    int privotKey = a[low];                             //基准元素  
	    while(low < high){                                   //从表的两端交替地向中间扫描  
	        while(low < high  && a[high] >= privotKey) --high;  //从high 所指位置向前搜索，至多到low+1 位置。将比基准元素小的交换到低端  
//	        swap(&a[low], &a[high]); 
	        int tmp = a[low];  
	        a[low] = a[high];  
	        a[high] = tmp; 
	        while(low < high  && a[low] <= privotKey ) ++low;  
	        int tmp2 = a[low];  
	        a[low] = a[high];  
	        a[high] = tmp2;  
	    }  
//	    print(a,10);  
	    return low;  
	}  
	

	/**
	 * 7,归并排序（Merge Sort）
	 * 
	 */
	//将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
	public static void Merge(int[] r,int[] rf, int i, int m, int n)  
	{  
	    int j,k;  
	    for(j=m+1,k=i; i<=m && j <=n ; ++k){  
	        if(r[j] < r[i]) rf[k] = r[j++];  
	        else rf[k] = r[i++];  
	    }  
	    while(i <= m)  rf[k++] = r[i++];  
	    while(j <= n)  rf[k++] = r[j++];  
//	    print(rf,n+1);  
	    //System.out.println(Arrays.toString(rf));
	}  
	  
	public static void MergeSort(int[] r, int[] rf, int lenght)  
	{   
		
	    int len = 1;  
	    int[] q = r ;  
	    int[] tmp ;  
	    while(len < lenght) {  
	        int s = len;  
	        len = 2 * s ;  
	        int i = 0;  
	        while(i+ len <lenght){  
	        	//System.out.println("          "+i);
	            Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
	            i = i+ len;  
	        }  
	        if(i + s < lenght){  
	        	//System.out.println("          "+i);
	            Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
	        }  
	        tmp = q; q = rf; rf = tmp; //交换q,rf，以保证下一趟归并时，仍从q 归并到rf  
	    }  
	}
	
	/**
	 * 这个排序排双数数组完全没问题呀
	 * @param r
	 * @param rf
	 * @param s
	 * @param t
	 */
	void MSort(int[] r, int[] rf,int s, int t)  
	{   
		int[] rf2 = null;  
	    if(s==t) r[s] = rf[s];  
	    else  
	    {   
	        int m=(s+t)/2;          /*平分*p 表*/  
	        MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
	        MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
	        Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
	    }  
	} 
	
	
	/**
	 * 8. 桶排序/基数排序(Radix Sort)
	 * 资料不全
	 */
	
//	public void RadixSort(int l[],int length,int maxradix)  
//	{  
//	   int m,n,k,lsp;  
//	   k=1;m=1;  
//	   int[][] temp = new int[10][length-1];  
////	   Empty(temp); //清空临时空间  
//	   while(k<maxradix) //遍历所有关键字  
//	   {  
//	     for(int i=0;i<length;i++) //分配过程  
//	    {  
//	       if(l[i]<m)  
//	          temp[0][n]=l[i];  
//	       else  
//	    	   lsp=(l[i]/m)%10; //确定关键字  
//	       temp[lsp][n]=l[i];  
//	       n++;  
//	   }  
//	   CollectElement(l,temp); //收集  
//	   n=0;  
//	   m=m*10;  
//	  k++;  
//	 }  
//	}  
//	
	
	
	
	
	
	
	
	
	public static void main(String[] args) {
//		double a[] = {1,11,2,9,3,7,5};
		int a[] = {1,11,-2,9,3,7,5,10};

//		int b[] = {2,12,10,4,6,8,13};
		int b[] = new int[a.length];
//		double[] asa = insertSort(a);
		
		//selectSort(a);
		heapSort(a, a.length);
//		bubbleSort(a, a.length);
//		bubble_1(a, a.length);
//		bubble_2(a, a.length);
//		quickSort(a, 0, a.length-1);
//		MergeSort(a, b, b.length);
		
		
		
		//System.out.println("======================");
		System.out.println(Arrays.toString(a));
		//System.out.println(Arrays.toString(b));
	}
	
	
	
	
	
}
